2025-10-08 Post-Quantum Cryptography
Generally our scenario is that the adversary has a quantum computer, but the users of the protocol do not.
Shor’s quantum algorithm breaks the Discrete Logarithm Problem, so it breaks most asymmetric cryptography.
Symmetric cryptography has less mathematical structure so quantum computers are less devastating, but [[Grover’s quantum algorithm]] still speeds up attacks.
UK Authorities Response
National Cyber Security Centre (NCSC)‘s timeline for UK businesses:
- By 2028, analyse how to migrate all systems to PQC
- By 2031, migrate all high-priority systems
- By 2035, migrate all systems
Hard problems for a post-quantum world
- Code-based encryption and signatures: uses error correcting codes. Short ciphertexts, large public keys.
- Hash-based signatures: uses hard-to-invert functions. Well-studied security, small public keys. Can’t do encryption yet.
- Isogeny-based encryption and signatures: based on finding maps between Elliptic Curves. Smallest keys, slow encryption, new.
- Lattice-based encryption and signatures: based on finding short vectors in high-dimensional lattices. Fastest encryption, huge keys, slow signatures.
- MPC-in-the-Head signatures: Multiparty Computation - think verified secret sharing.
- Multivariate signatures: based on solving simultaneous multivariate equations. Short signatures, large public keys, slow.
We do Diffie-Hellman Key Exchange by having walks in a graph. Secret keys are walks in the graph, and public keys are the end points of the walk. They then go to the other party’s endpoint and do their walk again. They then both arrive at the same point, the shared secret.
- Isogenies are a source of exponentially-sized graphs.
- We can walk efficiently on these graphs
- Fast mixing: short paths to (almost) all nodes
- No known efficient algorithms to recover paths from endpoints
- Enough structure to navigate the graph meaningfully
- Small keys, comparable to ECC keys.
- Millions of cycles per key exchange, 1000x as slow as the fastest pre-quantum key exchange.
- Published in 2018
- Isogenies are the smallest post-quantum key exchange idea. Also one of the slowest, and the newst.
- The only post-quantum NIKE - Non-interactive Key Exchange
- Lattices/codes construct a KEM
- More akin to message encryption than Diffie-Hellman
- Every post-quantum “key-exchange” except for CSIDH is actually a KEM
- Most protocols currently deployed using Diffie-Hellman don’t obviously work with KEMs
- For many applications the slow speed of CSIDH is also a deal-breaker
- Many papers on how to use KEMs for widely-deployed protocols. KEMTLS is a prominent example
Where are we now?
The NIST not-a-competition in September 2025:
- Key Exchange Finalists: CRYSTALS-KYBER* (lattices) and HQC (codes, closely related to KYBER)
- Signature Finalists
- CRYSTALS-DILITHIUM, Falcon (lattices)
- SPHINCS+ (hash-based)
- Key Exchange - fourth round
- BIKE, Classic McEcliece (codes)
SIKE (isogenies) - broken in fourth round
- Additional signatures competition started in June 2023
Asterisks
Ward Beullens found a new attack on multivariate cryptography after third round was announced. Ward broke the proposed parameters in a weekend on a laptop. Matthias Kannwischer and Lorenz Panny applied Ward’s algorithm to recover a secret key for abcmint. With smart design and large parameters, MV cryptography can be salvaged. See guest lecture for MAYO.
Castryck-Decru/Maino-Martindale/Robert found a new attack on SIKE after fourth round was announced.
Attacks on LWE (r.e. lattices) still an active research area. Attack direction could be devastating for Ideal-SVP: Bernstein-Lange. Failed but interesting quantum attack Chen.
What do we have?
- KEM/Encryption and signatures
- Diffie-Hellman-style / NIKE
- Fully Homomorphic Encryption (with lattices)
- Major protocols mostly understood how to transition
What don’t we have?
- Post-quantum for advanced
- Secure hardware implementation for new schemes
- Sufficient cryptanalysis
Further Reading